package com.xiyou.week01.linked;

/**
 * 21. 合并两个有序链表
 *
 * @ClassName：LeetCode21
 * @Author：西柚
 * @Date：2022/1/5 11:02 下午
 * @Versiion：1.0
 */
public class MergeTwoLists {

    /**
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     *
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            } else {
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }

        if (list1 == null) {
            cur.next = list2;
        } else {
            cur.next = list1;
        }

        return dummyHead.next;
    }

    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }

        if (list1.val < list2.val) {
            list1.next = mergeTwoLists2(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists2(list1, list2.next);
            return list2;
        }
    }

    //打印输出方法
    static void print(ListNode listNoed) {
        //创建链表节点
        while (listNoed != null) {
            System.out.println("节点:" + listNoed.val);
            listNoed = listNoed.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);    //创建首节点
        ListNode l1 = list1;                      //指向首节点
        ListNode list2 = new ListNode(1);    //创建首节点
        ListNode l2 = list2;                      //指向首节点

        //创建链表
        ListNode node = new ListNode(2);  //生成新的节点
        l1.next = node;
        l1 = l1.next;

        node = new ListNode(4);        //生成新的节点
        l1.next = node;
        l1 = l1.next;


        node = new ListNode(3);        //生成新的节点
        l2.next = node;
        l2 = l2.next;

        node = new ListNode(4);        //生成新的节点
        l2.next = node;
        l2 = l2.next;

//        print(mergeTwoLists(list1, list2));
        print(mergeTwoLists2(list1, list2));
    }
}
